GATE CSE 2004
Q21.
A 4-bit carry look ahead Combinational Circuit, which adds two 4-bit numbers, is designed using AND, OR, NOT, NAND, NOR gates only. Assuming that all the inputs are available in both complemented and uncomplemented forms and the delay of each gate is one time unit, what is the overall propagation delay of the Combinational Circuit? Assume that the carry network has been implemented using two-level AND-OR logic.Q22.
Given the following input (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) and the hash function x mod 10, which of the following statements are true? i) 9679, 1989, 4199 hash to the same value ii) 1471, 6171 has to the same value iii) All elements hash to the same value iv) Each element hashes to a different valueQ23.
A hard disk with a transfer rate of 10 Mbytes/second is constantly transferring data to memory using DMA. The processor runs at 600 MHz, and takes 300 and 900 clock cycles to initiate and complete DMA transfer respectively. If the size of the transfer is 20 Kbytes, what is the percentage of processor time consumed for the transfer operation?Q24.
Suppose each set is represented as a linked list with elements in arbitray order. Which of the operations among union, intersection, membership, cardinality will be the slowest?Q25.
A circularly linked list is used to represent a Queue. A single variable p is used to access the Queue. To which node should p point such that both the operations enQueue and deQueue can be performed in constant time?Q26.
The inclusion of which of the following sets into S = {{1, 2}, {1, 2, 3}, {1, 3, 5}, {1, 2, 4}, {1, 2, 3, 4, 5}} is necessary and sufficient to make S a complete lattice under the partial order defined by set containment?Q27.
Consider the following program fragment for reversing the digits in a given integer to obtain a new integer. Let n=d_{1}d_{2}...d_{m}. int n, rev; rev = 0; while (n > 0) { rev = rev*10 + n%10; n = n/10; } The loop invariant condition at the end of the i^{th} iteration is:Q28.
Consider the following C program main() { int x, y, m, n; scanf ("%d %d", &x, &y); /* Assume x > 0 and y > 0 */ m = x; n = y; while (m! = n) { if (m > n) m = m - n; else n = n - m; } print f ("% d", n); } The program computesQ29.
What does the following algorithm approximate? (Assume m \gt 1, e \gt 0). x = m; y = 1; while (x - y > e) { x = (x + y)/2; y = m/x; } print(x);Q30.
The relation scheme Student Performance (name, courseNo, rollNo, grade) has the following functional dependencies: name, courseNo, \rightarrow grade rollNo, courseNo \rightarrow grade name \rightarrow rollNo rollNo \rightarrow name The highest normal form of this relation scheme is